package algorithm_demo.demo01;


import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 *
 * @author Api
 * @date 2023/2/4 16:12
 */
public class Code27_ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    //第一种
    public static TreeNode buildTree2(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        Map<Integer, Integer> valueIndexMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            valueIndexMap.put(in[i], i);
        }
        return g(pre, 0, pre.length - 1, in, 0, in.length - 1, valueIndexMap);
    }


    public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2, Map<Integer, Integer> valueIndexMap) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        int find = valueIndexMap.get(pre[L1]);
        // x-(L1+1) = find-1-L2 最后得出L1 + find - L2（左子树的左边界）
        head.left = g(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);
        head.right = g(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, valueIndexMap);
        return head;
    }


    public static TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }

        return x(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }

    public static TreeNode x(int[] pre, int L1, int R1, int[] in, int L2, int R2, Map<Integer, Integer>map) {
        if (L1>R1){
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1==R1){
            return head;
        }
        int pIndex = map.get(pre[L1]);
        head.left = x(pre, L1+1, L1+pIndex-L2, in, L2, pIndex-1, map);
        head.right = x(pre, L1+pIndex-L2+1, R1, in, pIndex+1, R2, map);
        return head;
    }
}
